#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

// ======================== 类型定义 ========================

// 通用键值对结构
typedef struct KeyValuePair {
    void* key;
    void* value;
    struct KeyValuePair* next;
} KeyValuePair;

// HashMap结构
typedef struct {
    KeyValuePair** buckets;
    int size;
    unsigned int (*hash_func)(void*);
    int (*key_compare)(void*, void*);
} HashMap;

// 邻接表节点
typedef struct AdjListNode {
    void* node;
    struct AdjListNode* next;
} AdjListNode;

// 图节点信息
typedef struct {
    int in_degree;          // 当前入度
    int original_in_degree; // 原始入度（用于调试）
    AdjListNode* neighbors; // 邻接表
} NodeInfo;

// 批次结果
typedef struct BatchResult {
    void** nodes;           // 节点数组
    int count;              // 节点数量
    struct BatchResult* next;
} BatchResult;

// 拓扑排序结果
typedef struct {
    BatchResult* batches;   // 批次链表
    int total_batches;      // 总批次数
    int total_nodes;        // 总节点数
    bool has_cycle;         // 是否存在环
} TopoResult;

// ======================== 实用函数 ========================

// 判断一个数是否为质数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 查找大于等于给定整数的最小质数
int next_prime(int n) {
    if (n <= 2) return 2;
    if (n % 2 == 0) n++;
    while (!is_prime(n)) {
        n += 2;
    }
    return n;
}

// ======================== HashMap实现 ========================

// 创建HashMap
HashMap* hashmap_create(int size, 
                       unsigned int (*hash_func)(void*), 
                       int (*key_compare)(void*, void*)) {
    // 使用质数作为哈希表大小以获得更好的分布
    int prime_size = next_prime(size);
    
    HashMap* map = malloc(sizeof(HashMap));
    map->buckets = calloc(prime_size, sizeof(KeyValuePair*));
    map->size = prime_size;
    map->hash_func = hash_func;
    map->key_compare = key_compare;
    return map;
}

// 添加/更新键值对
void hashmap_put(HashMap* map, void* key, void* value) {
    unsigned int hash = map->hash_func(key) % map->size;
    KeyValuePair* pair = map->buckets[hash];
    
    // 检查键是否已存在
    while (pair) {
        if (map->key_compare(pair->key, key) == 0) {
            pair->value = value;
            return;
        }
        pair = pair->next;
    }
    
    // 创建新键值对
    KeyValuePair* new_pair = malloc(sizeof(KeyValuePair));
    new_pair->key = key;
    new_pair->value = value;
    new_pair->next = map->buckets[hash];
    map->buckets[hash] = new_pair;
}

// 获取值
void* hashmap_get(HashMap* map, void* key) {
    unsigned int hash = map->hash_func(key) % map->size;
    KeyValuePair* pair = map->buckets[hash];
    
    while (pair) {
        if (map->key_compare(pair->key, key) == 0) {
            return pair->value;
        }
        pair = pair->next;
    }
    return NULL;
}

// 检查键是否存在
bool hashmap_contains(HashMap* map, void* key) {
    return hashmap_get(map, key) != NULL;
}

// 释放HashMap
void hashmap_free(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        KeyValuePair* pair = map->buckets[i];
        while (pair) {
            KeyValuePair* next = pair->next;
            free(pair);
            pair = next;
        }
    }
    free(map->buckets);
    free(map);
}

// ======================== 图操作 ========================

// 初始化图
HashMap* graph_create(int expected_size, 
                     unsigned int (*hash_func)(void*), 
                     int (*key_compare)(void*, void*)) {
    return hashmap_create(expected_size, hash_func, key_compare);
}

// 添加节点
void add_node(HashMap* graph, void* node) {
    if (!hashmap_contains(graph, node)) {
        NodeInfo* info = malloc(sizeof(NodeInfo));
        info->in_degree = 0;
        info->original_in_degree = 0;
        info->neighbors = NULL;
        hashmap_put(graph, node, info);
    }
}

// 添加边到图中
void add_edge(HashMap* graph, void* from, void* to) {
    // 确保节点存在
    add_node(graph, from);
    add_node(graph, to);
    
    NodeInfo* from_info = hashmap_get(graph, from);
    
    // 创建邻接表节点
    AdjListNode* new_node = malloc(sizeof(AdjListNode));
    new_node->node = to;
    new_node->next = from_info->neighbors;
    from_info->neighbors = new_node;
    
    // 更新入度
    NodeInfo* to_info = hashmap_get(graph, to);
    to_info->in_degree++;
    to_info->original_in_degree++;
}

// 释放图内存
void graph_free(HashMap* graph) {
    // 遍历所有桶
    for (int i = 0; i < graph->size; i++) {
        KeyValuePair* pair = graph->buckets[i];
        while (pair) {
            NodeInfo* info = (NodeInfo*)pair->value;
            // 释放邻接表
            AdjListNode* neighbor = info->neighbors;
            while (neighbor) {
                AdjListNode* next = neighbor->next;
                free(neighbor);
                neighbor = next;
            }
            // 释放节点信息
            free(info);
            
            KeyValuePair* next_pair = pair->next;
            free(pair);
            pair = next_pair;
        }
    }
    free(graph->buckets);
    free(graph);
}

// ======================== 拓扑排序核心实现 ========================

// 执行拓扑排序
TopoResult* topological_sort(HashMap* graph) {
    // 初始化结果
    TopoResult* result = malloc(sizeof(TopoResult));
    result->batches = NULL;
    result->total_batches = 0;
    result->total_nodes = 0;
    result->has_cycle = false;
    
    // 计算总节点数
    int total_nodes = 0;
    for (int i = 0; i < graph->size; i++) {
        KeyValuePair* pair = graph->buckets[i];
        while (pair) {
            total_nodes++;
            pair = pair->next;
        }
    }
    
    // 入度为零的节点队列
    void** zero_indegree = malloc(total_nodes * sizeof(void*));
    int zero_count = 0;
    
    // 收集所有入度为零的节点
    for (int i = 0; i < graph->size; i++) {
        KeyValuePair* pair = graph->buckets[i];
        while (pair) {
            NodeInfo* info = pair->value;
            if (info->in_degree == 0) {
                zero_indegree[zero_count++] = pair->key;
            }
            pair = pair->next;
        }
    }
    
    // 主处理循环
    while (zero_count > 0) {
        // 创建新批次结果
        BatchResult* new_batch = malloc(sizeof(BatchResult));
        new_batch->nodes = malloc(zero_count * sizeof(void*));
        memcpy(new_batch->nodes, zero_indegree, zero_count * sizeof(void*));
        new_batch->count = zero_count;
        new_batch->next = result->batches;
        result->batches = new_batch;
        result->total_batches++;
        result->total_nodes += zero_count;
        
        // 下一批节点
        void** next_batch = malloc(total_nodes * sizeof(void*));
        int next_count = 0;
        
        // 处理当前批次的所有节点
        for (int i = 0; i < zero_count; i++) {
            void* node = zero_indegree[i];
            NodeInfo* info = hashmap_get(graph, node);
            
            // 减少邻居节点的入度
            AdjListNode* neighbor = info->neighbors;
            while (neighbor) {
                NodeInfo* neighbor_info = hashmap_get(graph, neighbor->node);
                if (--neighbor_info->in_degree == 0) {
                    next_batch[next_count++] = neighbor->node;
                }
                neighbor = neighbor->next;
            }
        }
        
        // 准备下一轮迭代
        free(zero_indegree);
        zero_indegree = next_batch;
        zero_count = next_count;
    }
    
    free(zero_indegree);
    
    // 检查是否存在环
    if (result->total_nodes < total_nodes) {
        result->has_cycle = true;
    }
    
    return result;
}

// 打印拓扑排序结果
void print_topo_result(TopoResult* result, void (*print_node)(void*)) {
    printf("\n===== 拓扑排序结果 =====\n");
    printf("总批次数: %d\n", result->total_batches);
    printf("总节点数: %d\n", result->total_nodes);
    printf("检测到环: %s\n\n", result->has_cycle ? "是" : "否");
    
    // 反转批次链表以便按顺序打印
    BatchResult* prev = NULL;
    BatchResult* current = result->batches;
    BatchResult* next = NULL;
    while (current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    result->batches = prev;
    
    BatchResult* batch = result->batches;
    int batch_num = 1;
    
    while (batch) {
        printf("批次 #%d (%d 个节点): [", batch_num++, batch->count);
        for (int i = 0; i < batch->count; i++) {
            print_node(batch->nodes[i]);
            if (i < batch->count - 1) printf(", ");
        }
        printf("]\n");
        batch = batch->next;
    }
    printf("\n");
}

// 释放拓扑排序结果
void free_topo_result(TopoResult* result) {
    BatchResult* batch = result->batches;
    while (batch) {
        BatchResult* next = batch->next;
        free(batch->nodes);
        free(batch);
        batch = next;
    }
    free(result);
}

// ======================== 示例使用 ========================

// 字符串哈希函数
unsigned int string_hash(void* key) {
    char* str = (char*)key;
    unsigned int hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash;
}

// 字符串比较函数
int string_compare(void* a, void* b) {
    return strcmp((char*)a, (char*)b) == 0;
}

// 打印字符串节点
void print_string_node(void* node) {
    printf("%s", (char*)node);
}

// 整数哈希函数
unsigned int int_hash(void* key) {
    int* num = (int*)key;
    // 简单哈希函数，实际应用中可使用更复杂的
    return *num * 2654435761; // 32位乘法哈希
}

// 整数比较函数
int int_compare(void* a, void* b) {
    int* num_a = (int*)a;
    int* num_b = (int*)b;
    return *num_a == *num_b;
}

// 打印整数节点
void print_int_node(void* node) {
    printf("%d", *(int*)node);
}

// 示例1：字符串节点
void example_with_strings() {
    printf("===== 字符串节点示例 =====\n");
    
    // 创建图
    HashMap* graph = graph_create(10, string_hash, string_compare);
    
    // 构建图
    add_edge(graph, "数据结构", "算法");
    add_edge(graph, "离散数学", "数据结构");
    add_edge(graph, "C语言", "数据结构");
    add_edge(graph, "算法", "操作系统");
    add_edge(graph, "计算机组成原理", "操作系统");
    add_edge(graph, "C语言", "计算机组成原理");
    add_edge(graph, "操作系统", "计算机网络");
    add_edge(graph, "操作系统", "数据库系统");
    add_edge(graph, "高等数学", "离散数学");
    add_edge(graph, "高等数学", "线性代数");
    add_edge(graph, "线性代数", "机器学习");
    add_edge(graph, "概率论", "机器学习");
    
    // 执行拓扑排序
    TopoResult* result = topological_sort(graph);
    
    // 打印结果
    print_topo_result(result, print_string_node);
    
    // 清理资源
    free_topo_result(result);
    graph_free(graph);
}

// 示例2：整数节点
void example_with_integers() {
    printf("===== 整数节点示例 =====\n");
    
    // 创建图
    HashMap* graph = graph_create(10, int_hash, int_compare);
    
    // 创建节点
    int nodes[10];
    for (int i = 0; i < 10; i++) {
        nodes[i] = i + 1;
    }
    
    // 构建图
    add_edge(graph, &nodes[0], &nodes[2]); // 1 -> 3
    add_edge(graph, &nodes[0], &nodes[3]); // 1 -> 4
    add_edge(graph, &nodes[1], &nodes[3]); // 2 -> 4
    add_edge(graph, &nodes[1], &nodes[4]); // 2 -> 5
    add_edge(graph, &nodes[2], &nodes[5]); // 3 -> 6
    add_edge(graph, &nodes[3], &nodes[5]); // 4 -> 6
    add_edge(graph, &nodes[3], &nodes[6]); // 4 -> 7
    add_edge(graph, &nodes[4], &nodes[7]); // 5 -> 8
    add_edge(graph, &nodes[5], &nodes[8]); // 6 -> 9
    add_edge(graph, &nodes[6], &nodes[8]); // 7 -> 9
    add_edge(graph, &nodes[7], &nodes[9]); // 8 -> 10
    add_edge(graph, &nodes[8], &nodes[9]); // 9 -> 10
    
    // 执行拓扑排序
    TopoResult* result = topological_sort(graph);
    
    // 打印结果
    print_topo_result(result, print_int_node);
    
    // 清理资源
    free_topo_result(result);
    graph_free(graph);
}

// 示例3：检测环
void example_with_cycle() {
    printf("===== 环检测示例 =====\n");
    
    // 创建图
    HashMap* graph = graph_create(5, string_hash, string_compare);
    
    // 构建带环的图
    add_edge(graph, "A", "B");
    add_edge(graph, "B", "C");
    add_edge(graph, "C", "D");
    add_edge(graph, "D", "B"); // 创建环 B->C->D->B
    
    // 执行拓扑排序
    TopoResult* result = topological_sort(graph);
    
    // 打印结果
    print_topo_result(result, print_string_node);
    
    // 清理资源
    free_topo_result(result);
    graph_free(graph);
}

int main() {
    example_with_strings();
    example_with_integers();
    example_with_cycle();
    return 0;
}